import bisect
class Solution(object):
    def maxTotalFruits(self, fruits, startPos, k):
        steps = []
        n = len(fruits)
        now = 0
        max_amount = float('inf')
        s_index = bisect.bisect_left(fruits, [startPos, 0])
        for i in range(s_index, n):
            dest= fruits[i][0] - startPos
            if dest <= k:
                now += fruits[i][1]
                steps.append([dest, now])
            else:
                break
        ans = now
        now = 0
        for i in range(s_index - 1, -1, -1):
            dest = startPos - fruits[i][0]
            if dest <= k:
                now += fruits[i][1]
                index = bisect.bisect_right(steps, [(k - dest) // 2, max_amount])
                if index > 0:
                    ans = max(now + steps[index - 1][1], ans)
                else:
                    ans = max(ans, now)
                if 2 * dest <= k:
                    index = bisect.bisect_right(steps, [k - 2 * dest, max_amount])
                    if index > 0:
                        ans = max(now + steps[index - 1][1], ans)
            else:
                break
        return ans

data = Solution()
# fruits = [[2,8],[6,3],[8,6]]
# startPos = 5
# k = 4
# print(data.maxTotalFruits(fruits, startPos, k))
fruits = [[1060,577],[1155,4703],[1243,590],[1366,4535],[1483,4010],[1612,6288],[1617,5807],[1654,7620],[1738,9269],[1753,674],[1774,8056],[1864,1266],[1930,8493],[1975,136],[2031,9733],[2040,2290],[2060,971],[2075,2168],[2271,8605],[2356,3652],[2389,372],[2395,5399],[2441,5821],[2443,9224],[2494,4962],[2507,7073],[2684,507],[2765,6223],[2876,3602],[2905,1351],[3262,3093],[3474,1224],[3535,8688],[3543,8930],[3584,9449],[3608,9841],[3654,3752],[3689,4732],[3710,3422],[3816,4946],[3993,3160],[4031,8656],[4086,2920],[4163,3618],[4204,8008],[4205,3857],[4374,5203],[4423,9151],[4428,6870],[4482,4646],[4648,5974],[4692,3845],[4702,40],[4855,5000],[4873,8112],[5072,1096],[5243,857],[5433,4260],[5471,1722],[5479,7220],[5485,8352],[5501,17],[5509,5546],[5530,5146],[5554,6626],[5680,5466],[5722,2083],[5739,7025],[6161,239],[6210,9177],[6267,8749],[6288,2860],[6372,4124],[6381,4651],[6416,4200],[6481,7002],[6534,7615],[6572,7503],[6674,1234],[6732,1627],[6765,8245],[6774,7526],[6776,4034],[6868,3198],[6928,7160],[6960,1604],[7101,7070],[7144,8126],[7228,6550],[7291,867],[7389,5365],[7468,3143],[7482,5700],[7729,1000],[7803,762],[7807,9658],[7813,477],[7825,5914],[8135,1619],[8201,2661],[8231,4020],[8295,5096],[8614,9731],[8616,1461],[8619,7263],[8675,1334],[8695,5425],[8840,9366],[8904,2341],[9005,531],[9248,2857],[9349,6923],[9361,6035],[9426,1309],[9546,2222],[9570,7522],[9589,3642],[9612,7496],[9797,7743],[9813,6949],[9877,1872],[9905,6133]]
startPos = 5500
k = 8785
print(data.maxTotalFruits(fruits, startPos, k))